package org.eda2;

import java.util.ArrayList;
import java.util.Collections;

// Esta clase pareto realiza mediante el algoritmo de divide y venceras,
// sucesivas lineas de pareto que van insertandondese en la solucion,
// hasta superar el minimo de usuarios, objetivo de la practica.
// Vamos a obtener de nuestra nube de usuarios, 2 grupos de usuarios,
// uno desde el primer usuario hasta el usuario cuyo consumo sea el minimo
// de todos los usuarios, el otro grupo estara compuesto por todos los
// usuarios desde el que consume menos haasta el ultimo de los usuarios.
// Sobre dichos grupos y aplicando el algoritmo DyV, obtendremos la linea de pareto
// mediante la combinacion de las distintas soluciones parciales a la recursividad
// realizada por el algoritmo DyV.
/**
 * Clase Pareto. Clase que realiza mediante la tecnica DyV o Greedy, mediante
 * lineas de pareto el estudio del problema de la practica.
 */
public class Pareto {

	/**
	 * The list. Hace referencia a la lista total de usuarios.
	 */
	private ArrayList<User> list;

	/**
	 * The userPareto. Hace referencia a la lista de usuarios que formaran parte
	 * del pareto
	 */
	private ArrayList<User> userPareto;

	/** The minElement. Hace referencia al usuario con el consumo menor. */
	private User minElement;

	/**
	 * The elementosMinimos. Hace referencia al numero minimo de elementos que
	 * formaran parte de nuestra solucion.
	 */
	private int elementosMinimos;

	/**
	 * Metodo Pareto. Metodo constructor de la clase. Inicializa un nuevo
	 * elemento de la clase.
	 * 
	 * @param in
	 *            . Variable de tipo ArrayList. Hace referencia a la lista de
	 *            usuarios a esudiar.
	 * 
	 */
	public Pareto(ArrayList<User> in) {
		// La lista de usuarios pasada por parametro...
		this.list = in;
		// El usuario con CE minimo...
		this.minElement = null;
		// Inicializamos la lista de los usuarios que formaran parte del
		// pareto...
		this.userPareto = new ArrayList<User>();
		// La cantidad minima de usuarios a estudiar....
		this.elementosMinimos = list.size() / 100;
	}

	/**
	 * Metodo paretoFrontier. Metodo que realiza la seleccion de los candidatos
	 * a estudiar de nuestra lista total de usuarios con la tecnica DyV.
	 * 
	 * @return userPareto. Variable de tipo ArrayList. Hace referencia a la
	 *         lista de usuarios a estudiar por la empresa.
	 */
	public ArrayList<User> paretoFrontier() {
		do {
			ArrayList<User> aux = new ArrayList<User>();
			// Volvemos a calcular el minimo para realizar una nueva
			// subdivision...
			this.minElement = Collections.min(list, new UserComparatorCE());
			// Dividimos la lista en 2 partes. Primera parte: paretoDown...
			aux.addAll(list.subList(0, list.indexOf(minElement) + 1));
			// Realizamos la llamada al algoritmo DyV de la primera parte...
			ArrayList<User> paretoDown = pareto(aux);
			aux.clear();
			// Segunda parte: paretoUp...
			aux.addAll(list.subList(list.indexOf(minElement), list.size()));
			// Le damos la vuelta para que sea igual a la primera parte...
			Collections.reverse(aux);
			ArrayList<User> paretoUp = pareto(aux);
			// Eliminamos el elemento de CE minimo....
			paretoUp.remove(paretoUp.size() - 1);
			// Insertamos en la lista de la solucion aquellos usuarios que han
			// salido candidatos a estudiar por la empresa electrica de la
			// practica...
			userPareto.addAll(paretoDown);
			userPareto.addAll(paretoUp);
			// Eliminamos de la lista inicial de los usuarios, aquellos
			// candidatos ya insertados en la solucion.
			list.removeAll(userPareto);
			// Realizamos el algoritmo DyV, tantas veces como sea necesario
			// hasta
			// alcanzar la cantidad minima exigida por la empresa para
			// estudiar...
		} while (userPareto.size() < elementosMinimos);
		Collections.sort(userPareto, new UserComparatorICE());
		return userPareto;
	}

	/**
	 * Metodo paretoFrontier. Metodo que realiza la seleccion de los candidatos
	 * a estudiar de nuestra lista total de usuarios de la solucion mejorada
	 * utilizando la tecnica DyV.
	 * 
	 * @param flag
	 *            . Variable de tipo int. Hace referencia a un valor bandera,
	 *            para distinguir los distintos metodos.
	 * @return userPareto. Variable de tipo ArrayList.
	 */

	public ArrayList<User> paretoFrontier(int flag) {
		do {
			ArrayList<User> aux = new ArrayList<User>();
			this.minElement = Collections.min(list, new UserComparatorCE());
			aux.addAll(list.subList(0, list.indexOf(minElement) + 1));
			ArrayList<User> paretoDown = pareto(aux, flag);
			aux.clear();
			aux.addAll(list.subList(list.indexOf(minElement), list.size()));
			Collections.reverse(aux);
			// Realizamos la llamada al pareto con la solucion mejorado...
			ArrayList<User> paretoUp = pareto(aux, flag);
			paretoUp.remove(paretoUp.size() - 1);
			userPareto.addAll(paretoDown);
			userPareto.addAll(paretoUp);
			list.removeAll(userPareto);
		} while (userPareto.size() < elementosMinimos);
		Collections.sort(userPareto, new UserComparatorICE());
		return userPareto;
	}

	/**
	 * Metodo paretoFrontierGreedy. Metodo que realiza la seleccion de los
	 * candidatos a estudiar de nuestra lista total de usuarios utilizando la
	 * tecnica Greedy.
	 * 
	 * @return userPareto. Variable de tipo ArrayList.
	 */
	public ArrayList<User> paretoFrontierGreedy() {

		do {
			ArrayList<User> aux = new ArrayList<User>();
			// Obtenemos el elemento con menor CE, para dividir nuestr nube de
			// usuarios en 2 partes...
			this.minElement = Collections.min(list, new UserComparatorCE());
			// Parte descendente...
			aux.addAll(list.subList(0, list.indexOf(minElement) + 1));
			ArrayList<User> paretoDown = new ArrayList<User>();
			// Obtenemos el primer elemento de la izquierda...
			User minUser = aux.get(0);
			paretoDown.add(minUser);
			for (int i = 1; i < aux.size(); i++) {
				// Vamos insertando todos los elementos de la derecha, que
				// tengan un CE superior al anterior, convirtiendose el nuevo
				// insertado en el nuevo comparador con el siguiente de la
				// derecha...
				if (minUser.getCe() >= aux.get(i).getCe()) {
					minUser = aux.get(i);
					paretoDown.add(minUser);
				}
			}
			aux.clear();
			// Parte ascendente...
			aux.addAll(list.subList(list.indexOf(minElement), list.size()));
			ArrayList<User> paretoUp = new ArrayList<User>();
			// Obtenemos el primer elemento de la derecha...
			minUser = aux.get(aux.size() - 1);
			paretoUp.add(minUser);
			for (int i = aux.size() - 2; i >= 0; i--) {
				// Vamos insertando todos los elementos de la izquierda, que
				// tengan un CE menor al anterior...
				if (minUser.getCe() >= aux.get(i).getCe()) {
					minUser = aux.get(i);
					paretoUp.add(minUser);
				}
			}
			paretoUp.remove(paretoUp.size() - 1);
			// Nuestra solucion del pareto sera la union de las 2 partes, la
			// ascendente y la descendente...
			userPareto.addAll(paretoDown);
			userPareto.addAll(paretoUp);
			// Dicha solucion parcial, sera eliminada de la lista inicial de
			// usuarios a estudiar...
			list.removeAll(userPareto);

			// Se realizara tantas veces como elementos minimos se pida en la
			// practica...
		} while (userPareto.size() < elementosMinimos);
		// Ordenamos la lista final de usuarios a estudiar por su ICE
		Collections.sort(userPareto, new UserComparatorICE());
		return userPareto;
	}

	/**
	 * Metodo pareto. Metodo que aplica el algoritmo DyV de la practica. Calcula
	 * los candidatos de las 2 partes, subdividiendo el problema en partes menos
	 * extensas. Una vez obtenemos en cada una de las partes los usuarios
	 * candidatos, mediante el metodo cambinar, unimos las 2 partes de los
	 * candidatos.
	 * 
	 * @param aux
	 *            . Variable de tipo ArrayList. Hace referencia a la lista de
	 *            usuarios pertenecientes a cada una de las partes.
	 * @return Variable de tipo ArrayList, con los usuarios de la lista inicial
	 *         candidatos al estudio por parte de la empresa.
	 */
	private ArrayList<User> pareto(ArrayList<User> aux) {
		// Caso BASE...
		if (aux.size() == 1) {
			return aux;
		}
		// RECURSIVIDAD...
		ArrayList<User> paretoLeft = new ArrayList<User>();
		ArrayList<User> paretoRight = new ArrayList<User>();
		// Dividimos los usuarios de la lista en 2 partes...
		paretoLeft.addAll(aux.subList(0, aux.size() / 2));
		paretoRight.addAll(aux.subList(aux.size() / 2, aux.size()));
		// Devolvemos la solucion de la combinacion de los 2 paretos...
		return combinar(pareto(paretoLeft), pareto(paretoRight));
	}

	/**
	 * Metodo pareto. Metodo que aplica el algoritmo DyV de la practica. Calcula
	 * los candidatos de las 2 partes, subdividiendo el problema en partes menos
	 * extensas. Una vez obtenemos en cada una de las partes los usuarios
	 * candidatos, mediante el metodo cambinar, unimos las 2 partes de los
	 * candidatos. Este algoritmo, esta mejorado respectoa al anterior, ya que
	 * elimina para las listas de las partes derechas, aquellos candidatos que
	 * tengan un CE superior al ultimo de la parte dercha.
	 * 
	 * @param aux
	 *            . Variable de tipo ArrayList. Hace referencia a la lista de
	 *            usuarios pertenecientes a cada una de las partes.
	 * @param flag
	 *            . Variable de tipo int. Hace referencia a un valor bandera,
	 *            para distinguir los distintos metodos.
	 * @return Variable de tipo ArrayList, con los usuarios de la lista inicial
	 *         candidatos al estudio por parte de la empresa.
	 */
	private ArrayList<User> pareto(ArrayList<User> aux, int flag) {
		// Caso BASE...
		if (aux.size() <= 1) {
			return aux;
		}
		// RECURSIVIDAD...
		ArrayList<User> paretoLeft = new ArrayList<User>();
		ArrayList<User> paretoRight = new ArrayList<User>();
		ArrayList<User> izq = new ArrayList<User>();
		ArrayList<User> der = new ArrayList<User>();
		// Insertamos la mitad de los usuarios en la izquierda....
		for (int i = 0; i < aux.size() / 2; i++) {
			paretoLeft.add(aux.get(i));
		}
		// Realizamos las sucesivas llamadas para la parte izquierda
		// (mejorado)...
		izq = pareto(paretoLeft, flag);

		// Realizamos la mejora del metodo, eliminado para para parte derecha,
		// todos aquellos usuarios, que tengan un CE superior al ultimo usuario
		// de la parte izquierda...
		// MEJORA
		for (int i = (aux.size() / 2); i < aux.size(); i++) {
			if ((izq.get(izq.size() - 1).getCe() >= aux.get(i).getCe())) {
				paretoRight.add(aux.get(i));
			}
		}
		// Realizamos las sucesivas llamadas para la parte derecha...
		der = pareto(paretoRight, flag);

		// Devolvemos la solucion de la combinacion de las 2 partes...
		return combinar(izq, der, flag);
	}

	/**
	 * Metodo combinar. Metodo que realiza la combinacion de la solucion de las
	 * 2 partes.
	 * 
	 * @param paretoLeft
	 *            . Variable de tipo ArrayList. Hace referencia a aquellos
	 *            usuarios candidatos de la parte izquierda.
	 * @param paretoRight
	 *            . Variable de tipo ArrayList. Hace referencia a aquellos
	 *            usuarios candidatos de la parte derecha. the pareto right
	 * @return paretoLeft.
	 */
	private ArrayList<User> combinar(ArrayList<User> paretoLeft,
			ArrayList<User> paretoRight) {
		// Condiciones anomalas de los conjuntos de entrada...
		if (paretoLeft.size() == 0 && paretoRight.size() == 0)
			return paretoRight;
		if (paretoLeft.size() == 0)
			return paretoRight;
		if (paretoRight.size() == 0)
			return paretoLeft;
		// Condicion ideal de combinacion...el ultimo de la izquierda sea mayor
		// que el primero de la dercha...unimos las partes completas.
		if (paretoLeft.get(paretoLeft.size() - 1).getCe() > paretoRight.get(0)
				.getCe()) {
			paretoLeft.addAll(paretoRight);
			// Devolvemos la lista...
			return paretoLeft;
		} else
		// Condicion en la que ambas listas sean unitarias...
		if (paretoLeft.size() == 1 && paretoRight.size() == 1) {
			// Si el usuario de la derecha tiene un CE superior al de la
			// izquierda...
			if (paretoLeft.get(0).getCe() < paretoRight.get(0).getCe()) {
				// Devolvemos la lista...
				return paretoLeft;
			}
			paretoLeft.addAll(paretoRight);
			// Devolvemos la lista....
			return paretoLeft;
		} else {
			// Condicion en la que el ultimo de la izquierda sea menor que
			// alguno
			// de los primeros de la parte derecha...
			while (paretoLeft.get(paretoLeft.size() - 1).getCe() < paretoRight
					.get(0).getCe()) {
				// Vamos eliminando el primero de la derecha, hasta que dicho
				// primero sea un usuario de menor CE que el ultimo de la
				// izquierda...
				paretoRight.remove(0);
				if (paretoRight.size() == 0)
					break;
			}
			paretoLeft.addAll(paretoRight);
			// Devolvemos la lista....
			return paretoLeft;
		}
	}

	/**
	 * Metodo combinar. Metodo que realiza la combinacion de la solucion de las
	 * 2 partes.
	 * 
	 * @param paretoLeft
	 *            . Variable de tipo ArrayList. Hace referencia a aquellos
	 *            usuarios candidatos de la parte izquierda.
	 * @param paretoRight
	 *            . Variable de tipo ArrayList. Hace referencia a aquellos
	 *            usuarios candidatos de la parte derecha. the pareto right
	 * @param flag
	 *            . Variable de tipo int. Hace referencia a una marca o valor
	 *            bandera, para diferencia el metodo mejorado respecto al
	 *            normal. the flag
	 * @return paretoLeft. Varaible de tipo ArrayList. Hace referencia a la
	 *         solucion final de candidatos a estudio por parte de la empresa.
	 */
	private ArrayList<User> combinar(ArrayList<User> paretoLeft,
			ArrayList<User> paretoRight, int flag) {
		// Con la solucion mejorada, el metodo combinar tan solo consiste en
		// insertar los partes completas, por lo que la parte derecha se la
		// insertamos a la parte izquierda.
		paretoLeft.addAll(paretoRight);
		// Devolvemos la solucion.
		return paretoLeft;
	}
}
